package com.lw.leetcode.bit.c;

import com.lw.test.util.Utils;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 6127. 优质数对的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/25 9:46
 */
public class CountExcellentPairs {

    public static void main(String[] args) {
        CountExcellentPairs test = new CountExcellentPairs();

        // 0
//        int[] arr = {5, 1, 1};
//        int k = 10;

        // 0
//        int[] arr = {1, 2, 3, 1};
//        int k = 3;

        // 0
        int[] arr = Utils.getArr(10000, 1, 10000000);
        int k = 4;

        long l = test.countExcellentPairs(arr, k);
        System.out.println(l);
    }

    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int[] counts = new int[32];
        long sum = 0;
        for (int num : set) {
            int c = Integer.bitCount(num);
            int t = Math.max(0, k - c);
            for (int i = t; i < 32; i++) {
                sum += (counts[i] << 1);
            }
            if (c + c >= k) {
                sum++;
            }
            counts[c]++;
        }
        return sum;
    }

}
